\section{链表}
\subsection{两数相加}
\begin{example}[两数相加]
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。如\figref{fig:addTwoNumbers}。
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
\end{example}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{addTwoNumbers}
	\caption{链表求和}
	\label{fig:addTwoNumbers}
\end{figure}
\begin{Mind}{链表求和}{}
	因为链表的末尾表示高位，而加法运算对低位对齐。所以只需要两个指针指向链表的头，分别计算进位和和然后更新并向前推进即可。问题在于当两个链表长度不同的时候短链表消耗完之后只有进位和长链表的元素求和计算。
\end{Mind}
\begin{longlisting}
	\caption{链表求和}
	\cppfile[firstline=472,lastline=489]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:addTwoNumbers}
\end{longlisting}
\coderef{code:addTwoNumbers} 代码中核心在于480行两个节点可能有两个节点中又一个空个两个节点都不为空。此时前者的差异在于是否加上另一个求和元素。
\subsection{删除排序链表中的重复元素 II}
\begin{example}[删除排序链表中的重复元素 II]
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{deleteDuplicates}
	\caption{删除排序链表中的重复元素}
	\label{fig:deleteDuplicates}
\end{figure}
\begin{Mind}{删除排序链表中的重复元素 II}{}
	创建一个新的元素为-1的节点作为PreNode。然后用两个节点CurrentNode和NextNode分别指向链表头。移动NextNode，找到第一个值和CurrentNode不相同的节点。根据情况确定：
	\begin{itemize}
		\item NextNode移动超过了一个位置，则有重复元素。
		\item 移动了一个位置，无重复元素。
	\end{itemize}
	根据有无重复元素来确定PreNode的下一个位置是指向第一个和下一个元素不同的节点（删除了重复的元素），然后对剩余节点使用相同的办法判断。
\end{Mind}
\begin{longlisting}
	\caption{删除排序链表中的重复元素}
	\cppfile[firstline=492,lastline=520]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:deleteDuplicates}
\end{longlisting}
\subsection{反转链表}
\begin{example}[翻转链表]
	翻转链表，如果让后面的元素直接指向前面的元素会出现元素后面的元素无法访问，因为链表只能顺序访问。所以必须将后一个节点保存。
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.6\textwidth]{reverse_link}
		\caption{反转链表}
	\end{figure}
	整个反转操作需要保存当前节点的前一个节点pPrenode，后一个节点pNext，通过当前节点向后移动。直到pNext为nullptr则表明pNext到达链表末尾。此时反转后链表头为当前节点。操作如\figref{fig:reverselink}。
	\begin{figure}
		\centering
		\includegraphics[width=.6\textwidth]{reverselink}
		\caption{反转链表操作}
		\label{fig:reverselink}
	\end{figure}
\end{example}
实现\coderef{code:reverseList}。
\begin{longlisting}
	\caption{反转链表}
	\cppfile[firstline=26,lastline=39]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:reverseList}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度：$O(n)$ 。 假设 $n$ 是列表的长度，时间复杂度是 $O(n)$。
	\item 空间复杂度：$O(1)$ 。
\end{itemize}
\subsection*{反转链表（递归）}
通过不断传入head->next指向的节点，指向最后一个元素tail。获取最后一个元素，此时head栈中保留的是最后一个元素的前一个元素。head->next->next就能实现最后一个元素（4）和前一个元素（3）的反转，但是此时是双向指针，需要将前一个指针指向nullptr。此时反转完成，退栈，此时栈中保留的元素是当前元素的前一个元素（2先入后出）。反复递归调用即可实现反转。函数调用栈帧变化如\figref{fig:linkstack}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{linkstack}
	\caption{递归函数栈帧变化}
	\label{fig:linkstack}
\end{figure}
递归反转的逻辑图如\figref{fig:reverselin_rec}第四（k）个节点已经反转，这时候需要将第三（k-1）个节点指向其前一个节点（$P_{k-1}->next(P_{k-2})->next = P_{k-1}$）
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{reverselink_rec}
	\caption{递归反转链表流程}
	\label{fig:reverselin_rec}
\end{figure}
递归实现反转链表：
\begin{longlisting}
	\caption{反转链表（递归实现）}
	\cppfile[firstline=41,lastline=48]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:reverseList}
\end{longlisting}时间复杂度：$O(n)$ 。 假设 n 是列表的长度，那么时间复杂度为 $O(n)$。空间复杂度：$O(n)$ 。 由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。
\subsection{链表排序}
\begin{example}[链表排序]
给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。
\end{example}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{mergeLink}
	\caption{链表排序}
	\label{fig:mergeLink}
\end{figure}
\begin{Mind}{链表排序算法}{}
	将链表切分为两段，这两段不是有序的（只有一个元素的时候肯定是有序的）则继续切分。然后切分到有序之后合并有序链表最终返回合并之后的链表。示意图如\figref{fig:mergeSortAlgo}。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{mergeSortAlgo}
	\caption{拆分后合并有序数组实现排序}
	\label{fig:mergeSortAlgo}
\end{figure}
\begin{longlisting}
	\caption{链表排序实现}
	\cudafile[firstline=282,lastline=303]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:link_sort}
\end{longlisting}
注意\coderef{code:link_sort}中297行需要实现一个有序链表合并。
\subsection{融合链表}
\begin{example}[融合链表]
融合两个有序元素链表并保持链表元素的顺序。
\end{example}
\begin{Mind}{融合链表算法}{}
通过定义融合后的节点pMergehead,当链表A的头节点的数据小于B的头节点数据的时候下一步融合的是A的下一个节点组成的链表和B链表。融合后的节点pMergehead指向的即两个融合之后的结果，反复递归调用，直到两个链表都到了链表尾部融合终止。需要注意的是，两个参数分别指向两个链表的融合节点，当某一个节点指向nullptr的时候表示这个链表已经达到了末尾，同时意味着另一个链表没有达到末尾，这时候返回没有达到末尾的节点。
\end{Mind}
\begin{longlisting}
	\caption{融合链表（递归实现）}
	\cppfile[firstline=50,lastline=64]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:mergeLinker}
\end{longlisting}
时间复杂度$O(m+n)$，空间复杂度$O(m+n)$。
\begin{Mind}{递归实现链表融合}{}
创建指向链表头的指针节点，通过不断对比两个链表的元素，用prenode指向其中元素较小的节点，反复调用直到任何一个链表到达链表尾部。这时候另一个链表还没有到达尾部，需要判断一下prenode下一个节点指向的节点是否为l1且为空，是则指向l2否则指向l1。算法处理如\figref{fig:merge_link_rec}：
\end{Mind}
\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{merge_link_rec}
	\caption{迭代融合链表}
	\label{fig:merge_link_rec}
\end{figure}

\begin{longlisting}
	\caption{融合链表}
	\cppfile[firstline=66,lastline=83]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:mergeLinker}
\end{longlisting}
时间复杂度$O(m)+O(n)$，空间复杂度$O(1)$
\subsection{链表中的公共节点}
\begin{example}[链表中的第一个公共节点]
	找到链表中第一个公共节点。
\end{example}
\begin{Mind}{链表中的公共节点}{}
遍历两个链表获取链表长度m,n，对长的链表m先前进(m-n),然后两个链表的指针同时往后移发现相同的节点即返回。示意\figref{fig:getIntersectionNode}。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{getIntersectionNode}
	\caption{公共节点}
	\label{fig:getIntersectionNode}
\end{figure}
双指针实现：
\begin{enumerate}
	\item 如果指针头不为空，同时移动到下一个节点。
	\item 如果a指针为空b不为空，则a指向b的头，如果b指针为空a不为空，移动到a的头。
	\item a、b同时为空则没有找到，a、b同时不为空则找到。
\end{enumerate}
实现如\coderef{code:fisrtCommonNode}
\begin{longlisting}
	\caption{第一个公共节点}
	\cppfile[firstline=85,lastline=93]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:fisrtCommonNode}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(1)。
\end{itemize}
\subsection{分隔链表}
\begin{example}[分隔链表]
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 <x 的节点都出现在x和大于x的元素之前，保持之前的大于x元素的顺序。 
\end{example}
\begin{figure}[!htbp]
	\centering
        \includesvg[width=.5\textwidth]{partition}
        \caption{分隔链表}
	\label{fig:partition}
\end{figure}
\begin{Mind}{分隔链表}{}
使用两个指针分别指向<x的元素和$\geq$x的元素。最终将小于指针的最后一个元素指向另一个指针头即可。
\end{Mind}
\begin{longlisting}
	\caption{分隔链表}
	\cppfile[firstline=313,lastline=346]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:partition}
\end{longlisting}
\coderef{code:partition}实现中有几个注意点：
\begin{enumerate}
	\item 更大的那个指针的最尾部元素需要指向空。
	\item 如果更小的那个指针头没有变动，最后结果应该是更大的那个指针头。
	\item 实现不同，代码里面通过分支处理了对头指针的记录，也可以创建一个空节点指向头，然后最后不用这个头。因为实现中不同位置分配内存可能会代码提交系统的内存回收错误。所以这里没有构建新节点。
\end{enumerate}

\subsection{旋转链表}
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.6\textwidth]{rotateRight}
	\end{center}
	\caption{旋转链表}
	\label{fig:rotateRight}
\end{figure}
\begin{Mind}{旋转链表思路}
	记给定链表的长度为 n，注意到当向右移动的次数 k。当$k\geq n$时，我们仅需要向右移动 k mod n 次即可。因为每 n 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第1
	个节点（从 0 开始计数）。这样我们可以先将给定的链表连接成环，然后将指定位置断开。具体代码中，我们首先计算出链表的长度 n，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后我们找到新链表的最后一个节点（即原链表的第
	(n−1)−(k mod n) 个节点），将当前闭合为环的链表断开，即可得到我们所需要的结果。特别地，当链表长度不大于1或者是 n 的倍数时，新链表将与原链表相同，我们无需进行任何处理。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{rotateLinkWithCircle}
	\caption{旋转链表示意图}
	\label{fig:rotateRightCircle}
\end{figure}
实现\coderef{code:rotateRightCircle}。
\begin{longlisting}
	\caption{旋转链表}
	\cppfile[firstline=209,lastline=233]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:rotateRightCircle}
\end{longlisting}
\subsection{环形链表判断}
\begin{example}[环形链表判断]
	给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。示意图如\figref{fig:isCycle}，图中2->0->4->2形成了环。
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{isCycle}
	\caption{是否存在环}
	\label{fig:isCycle}
\end{figure}
\begin{Mind}{是否存在环}{}
快慢指针，一个指针每次移动一下，一个移动两下，遇到环之前快慢指针的差距移动一次则+1，遇到环之后则每次-1。如果指向相同的元素则出现了环。
\end{Mind}
实现如\coderef{code:hasCycle}。
\begin{longlisting}
	\caption{是否存在环}
	\cppfile[firstline=95,lastline=114]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:hasCycle}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(1)。
\end{itemize}
\subsection{链表中环的入口节点}
\begin{example}[链表中环的入口节点]
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回nullptr。
\end{example}
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.6\textwidth]{entryNodeOfLoop}
	\end{center}
	\caption{链表中的环的入口节点}
	\label{fig:entryNodeOfLoop}
\end{figure}
\begin{Mind}{链表中的环}
	快慢指针，第一次相遇的时候一定在环内，此时将快指针移到链表头，然后快慢指针每次移动一个节点，相遇的地方就是环的入口。
\end{Mind}
代码实现\coderef{code:entryNodeOfLoop}：
\begin{longlisting}
	\caption{链表环的入口节点}
	\cppfile[firstline=235,lastline=262]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:entryNodeOfLoop}
\end{longlisting}
\subsection{链表中倒数第k个节点}
\begin{example}[链表中倒数第k个节点]
链表中倒数第k个节点。
\end{example}
\begin{Mind}{链表中倒数第k个节点}{}
双指针，指针first指向链表头，指针second指向链表后k个位置。然后两个指针同时移动，一旦second到达链表末尾则第一个指针指向的位置就是倒数k。
\end{Mind}
\begin{longlisting}
	\caption{链表中倒数第k个节点}
	\cppfile[firstline=116,lastline=132]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:kthEnd}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(1)。
\end{itemize}
% \subsection{删除链表中重复元素}
% \begin{example}[删除链表中重复元素]
% 删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次。例如：给出的链表为1->1->2删除后为1->2。
% \end{example}
% 算法实现(\figref{fig:deleteDuplicates})：遍历链表，如果下个节点不为nullptr则
% \begin{enumerate}
% 	\item 如果下个节点和当前节点值相同，则当前节点指向下个节点的next。
% 	\item 如果不同则不重复，往后移动一个节点。
% \end{enumerate}
% \begin{figure}[!htbp]
% 	\begin{center}
% 		\includegraphics[width=0.6\textwidth]{figures/deleteDuplicates}
% 	\end{center}
% 	\caption{删除重复节点示意图}
% 	\label{fig:deleteDuplicates}
% \end{figure}
% \begin{itemize}
% 	\item 时间复杂度O(n)。
% 	\item 空间复杂度O(1)。
% \end{itemize}
\subsection{回文链表}
\begin{example}[回文链表]
	给定一个链表的 头节点 head ，请判断其是否为回文链表。
\end{example}
\begin{Mind}{回文链表实现}{}
数据结构实现，遍历链表找到中间位置。然后将链表之前的元素加入栈，最后通过栈中元素和链表中元素逐一对比存在不相同元素则为false，否则为true。
\end{Mind}
\begin{longlisting}
	\caption{回文链表判断}
	\cppfile[firstline=149,lastline=182]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:isPali}
\end{longlisting}
\subsection{删除链表中的倒数第n个节点}
\begin{example}[删除链表中的倒数第n个节点]
删除链表的倒数第 n 个结点。head = [1,2,3,4,5], n = 2。输出[1,2,3,5]。需要注意的是head = [1]，n=1输出nullptr。
\end{example}
\begin{Mind}{删除链表第n个节点}{}
找到倒数第n个节点，和它的上一个节点，将上一个节点指向其下一个节点。删除头节点时有点不同，如果是头结点，则直接将头更新到节点的下一个节点即可，实现如\coderef{code:removeNthFromEnd}。
\end{Mind}
\begin{itemize}
	\item 时间复杂度：O(n)。
	\item 空间复杂度：O(1)。
\end{itemize}
\begin{longlisting}
	\caption{删除倒数第n个节点}
	\cppfile[firstline=184,lastline=207]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:removeNthFromEnd}
\end{longlisting}
\subsection{k个一组翻转链表}
\begin{example}[k个一组翻转链表]
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。输入：head = [1,2,3,4,5], k = 2
	输出：[2,1,4,3,5]。示意图如\figref{fig:reverseKGroup}。
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{reverseKGroup}
	\caption{k个一组翻转链表}
	\label{fig:reverseKGroup}
\end{figure}
\begin{Mind}{k个一组翻转链表}{}
从链表开头，依次向后移动，当移动k次之后到达。然后需要将前k个节点反转。这时候需要一个节点记录当前k个节点的最后一个节点，将其切断之后反转（切断之后会导致下一个节点丢失，所以下一个节点也应该保存）。这样就能反转第一个k。然后将切断的链表连上。第一段需要确定反转之后的头，剩下的段需要确定上次反转的尾。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{reverseKGroupAlgo}
	\caption{k个一组翻转链表}
	\label{fig:reverseKGroupAlgo}
\end{figure}
\begin{enumerate}
	\item 算法k\_tail保存上一段的尾，k\_head保存下一段的头，k\_node和current用来迭代保存段后一个元素和下一段第一个元素。
	\item k\_node移动到对的位置之后，切断和后面的联系。
	\item 反转这k个节点。因为这是第一段，所以new\_head保存反转之后的头。然后用段的最后一个元素连上上一步切断的节点。代码400行。
	\item k\_node移动到下一个位置、k\_tail记录当前段的最后一个元素、k\_head记录下一段的第一个元素。\figref{fig:reverseKGroupAlgo}步骤1整体操作完成。
	\item 第二轮和第一轮一样，不同在于指向下段头的时候是上一段的尾而不是new\_head。其中是否是第一段是通过变量reverse\_count判断的。
\end{enumerate}
\begin{longlisting}
	\caption{k个一组翻转链表}
	\cppfile[firstline=378,lastline=409]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:removeNthFromEnd}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150}{随机链表的复制}}
\begin{example}[随机链表的复制]
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random\_index] 表示：
\begin{itemize}
	\item val：一个表示 Node.val 的整数。
	\item random\_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
\end{itemize}
你的代码 只 接受原链表的头节点 head 作为传入参数。
\end{example}
此问题的麻烦之处在于节点的 next 指针指向的位置是确定的，但是随机指向的是不确定的。可能出现节点的随机指针指向一个还没有被创建的节点。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{copyRandomList}
	\caption{带随机指针的链表示意图}
	\label{fig:copyRandomList}
\end{figure}
\begin{Mind}{带随机指针的链表复制}{}
遍历节点，对每一个节点复制其next节点和random节点。为了保证复制random节点的时候已经存在节点，我们使用cache缓存当前节点。如果节点被缓存过则复制random指向的节点的时候直接从缓存中获取数据即可。
\end{Mind}
\begin{longlisting}
	\caption{复制带随机指针的链表（缓存实现）}
	\cudafile[firstline=451,lastline=469]{third_party/coding/cxx/algorithm/datastruct/src/linker_operator.cc}
	\label{code:copyRandomList}
\end{longlisting}

